题目分析

这个题目是一个贪心问题，有思路很好写，没有思路就非常困难，能难倒你们吗？

排序

我们观察样例，假如有a < b < c < d四个数，那么应该如何配对呢？如果a和谁配对，那么最小值都是a，因此我们尽量让a和次小值b配对，如果a不和b配对，假设a和c或者d配对，那么b就和d或者c配对，那么之和为a+b，如果a和b配对，那么之和为a+c，是大于a+b的，因此我们要让最小的两个数配对。那么多组数也是同理。

因此我们可以让数组进行排序，0，1为一组，2，3为一组，这样排序后nums[0] < nums[1]，nums[2] < nums[3]。因此我们把下标为偶数的求和，即可得到最后的结果。

算法的**时间复杂度为$O(nlog(n))$，空间复杂度为$O(1)$**。

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int res = 0;
        for (int i = 0; i < nums.size(); i += 2) { res += nums[i]; }
        return res;
    }
};

计数排序

排序方法有很多，在这里不一一列举，常见的10种排序方法在Leetcode912题有详细介绍。这里主要说一下计数排序的思路。

因为这个题目已经告诉了我们整数的范围，范围不是很大，sort排序算法的时间复杂度是$O(nlog(n))$的，而计数排序特别适合于整数范围不大的情况，因此可以进行优化。

我们统计每个元素出现次数，然后从小到大取出，在取出的过程中只取出下标为偶数的值即可。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        int array[20001], init = -10000, res = 0, idx = 0;
        memset(array, 0, sizeof(array));
        for (int x : nums) { array[x - init]++; }
        for (int i = init; i <= 10000; i++) {
            while (array[i - init]--) { res += (++idx % 2) * i; }
        }
        return res;
    }
};

刷题总结

排序是数组类型题目的常考知识点，当我们看到数据范围在1e4~1e7，我们要想到排序方法，在这个范围内$O(nlog(n))$的算法恰好满足条件，当数据范围达到1e8时，我们就不能用系统的排序方案，只能去寻找线性时间复杂度的解法。希望小伙伴们要有这个反应和判断。因为在笔试中，往往都会告诉我们数据的范围，因此这个能力非常重要。